﻿/**	std_vector.hpp
 *	----	Create Time Stamp	--2007-05-04 20:53:25--
 *------------------------------------------------------------------------------
 *	Mean	:不会抛出异常的东西， 因此和标准肯定是有出入的
 *	Author	:Nick Shallery	(nicknide@gmail.com)
 *	Version	:1.0.24.30	(2009-08-14 21:44:48)
 *------------------------------------------------------------------------------
**/	/*YOU HAVE ALL LEFT WITH THIS CODE WHILE YOU KEEP COMMENT IN EVERY COPY.*/


#if			!defined(__LOLIX__TOY__STD_VECTOR__NICK__K_IN_G__)
#define		__LOLIX__TOY__STD_VECTOR__NICK__K_IN_G__
//==============================================================================
//--------------------------------------------------------------------------

#if			!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)
	#include	"../lolix_cfg.h"
#endif	//	!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)

#if			!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)
	#include	"./allocator.h"
#endif	//	!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)
#if			!defined(__LOLIX__TOY__L_X_ASSERT_NICK__K_IN_G__)
	#include	"./lx_assert.h"
#endif	//	!defined(__LOLIX__TOY__L_X_ASSERT_NICK__K_IN_G__)
#if			!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)
	#include	"./std_algorithm.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_ALGORITHM__NICK__K_IN_G__)
#if			!defined(__LOLIX__TOY__STD_ITERATOR__NICK__K_IN_G__)
	#include	"./std_iterator.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_ITERATOR__NICK__K_IN_G__)


#if			defined(LOLIX_CFG__IS_DEBUG) || defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)
	#define		__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO
#endif	//	defined(LOLIX_CFG__IS_DEBUG) || defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)

#if			!defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)
	#define		__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR
#endif	//	!defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)

#if			LOLIX_CFG__IS_DEBUG
	#define		__LOLIX_TMP__DEFINE__CHECK_VALID(v)	__check_valid(v)
#else	//	LOLIX_CFG__IS_DEBUG
	#define		__LOLIX_TMP__DEFINE__CHECK_VALID(v)
#endif	//	LOLIX_CFG__IS_DEBUG

namespace lolix{namespace toy{
template<typename _Ty, typename _Alc>class vector;

namespace _help{
template< typename _Ty, typename _Alc>
class _vector_base
{
	typedef _vector_base<_Ty, _Alc> this_type;
	typedef	typename _Alc::rebind<_Ty>::other	_AlT;
public:
	typedef				_Alc allocator_type;
	typedef typename	_AlT::size_type			size_type;
	typedef typename	_AlT::difference_type	difference_type;
	typedef typename	_AlT::pointer			pointer;
	typedef typename	_AlT::const_pointer		const_pointer;
	typedef typename	_AlT::reference			reference;
	typedef typename	_AlT::const_reference	const_reference;
	typedef typename	_AlT::value_type		value_type;

private:
	class	_T_CIterator
		{
			friend	_vector_base<_Ty, _Alc>;
			typedef	_T_CIterator					this_type;
		public:
			typedef std::random_access_iterator_tag iterator_category;
			typedef _Ty								value_type;
			typedef difference_type					difference_type;
			//typedef difference_type					distance_type;	// retained
			typedef pointer							pointer;
			typedef reference						reference;
			typedef const_pointer					const_pointer;
			typedef const_reference					const_reference;

			LOLIX_INLINE_CALL	_T_CIterator(void)
				{
#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
				_ptr = 0;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				_vec = 0;
				_pos = 0;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				}
			LOLIX_INLINE_CALL	~_T_CIterator(void){}

			LOLIX_INLINE_CALL	const_reference operator*(void)const
				{
				return *__get();
				}

			LOLIX_INLINE_CALL	const_pointer operator->(void)const
				{
				return __get();
				}

			LOLIX_INLINE_CALL	this_type& operator ++(void)
				{
				return (*this).operator += (1);
				}
			LOLIX_WARNING_FOR_PERFORMANCE("use prefix increment operator instead")
			LOLIX_INLINE_CALL	this_type operator ++(int)
				{
				this_type tmp(*this);
				++(*this);
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type&	operator --(void)
				{
				return (*this).operator -= (1);
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix decrement operator instead")
			LOLIX_INLINE_CALL	this_type	operator --(int)
				{
				this_type tmp(*this);
				--(*this);
				return tmp;
				}
			LOLIX_INLINE_CALL	this_type&	operator += (difference_type pos)
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				_pos += pos;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)

#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
				_ptr += pos;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type&	operator -= (difference_type pos)
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				_pos -= pos;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)

#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
				_ptr -= pos;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type	operator + (difference_type pos)const
				{
				this_type tmp(*this);
				tmp += pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type	operator - (difference_type pos)const
				{
				this_type tmp(*this);
				tmp -= pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	difference_type	operator-(const this_type& o)const
				{
				DO_IN_DEBUG_MODEL(__check_same_ct(o));
				return this->__get() - o.__get();
				}

			LOLIX_INLINE_CALL	const_reference operator[](difference_type pos)const
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(pos);
				return *(this->__get()+pos);
				}
#undef		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC
#define		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(__lx_v__)		\
			LOLIX_INLINE_CALL	bool operator __lx_v__ (const this_type& o)const{DO_IN_DEBUG_MODEL(__check_same_ct(o));return this->__get() __lx_v__ o.__get();}
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(==);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(!=);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(<);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(<=);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(>);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(>=);
#undef		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC

		protected:
			LOLIX_INLINE_CALL	_T_CIterator(const _vector_base<_Ty, _Alc>& o, size_type pos)
				{
#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
				_ptr = o._val + pos;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)

#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				_vec = &o;
				_pos = pos;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);
				}

			LOLIX_INLINE_CALL	const const_pointer __get(void)const
				{
				__LOLIX_TMP__DEFINE__CHECK_VALID(0);

#if			defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)
				return _vec->_val + _pos;
#else	//	defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)
				return _ptr;
#endif	//	defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)
				}


#if			defined(_DEBUG)
			LOLIX_INLINE_CALL	void __check_valid(difference_type pos)const
				{
				const char* war = "invalid lolix::toy::iterator/const_iterator/reference\nbe careself.";
#if			defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)
				LOLIX_ASSERT(	_vec
								&& _vec->_size >= _pos	//	引用对象存在， 并且当前范围没有溢出
								&& _pos + pos <= _vec->_size
								&& _pos + pos >= 0
							,	war);
#endif	//	defined(LOLIX_CFG__SELF_VECTOR_PROTECT_ITERATOR)
				}

			LOLIX_INLINE_CALL	void	__check_same_ct(const this_type& o)const
				{
#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				LOLIX_ASSERT(_vec == o._vec, "invalid container from two lolix::toy::iterator/const_iterator.");
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
				}
#endif	//	defined(_DEBUG)

			//	其实直接使用下面这样子迭代器就不会失效了， 不过为了“友好”起见，还是失效好了， 毕竟那样才是标准实现啊
#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)
			const _vector_base<_Ty, _Alc>*		_vec;
			size_type							_pos;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_CNT_INFO)

#if			defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
			const_pointer						_ptr;
#endif	//	defined(__LOLIX__SELF_VECTOR_ITERATOR_HAVE_PTR)
		};
	friend	_T_CIterator;

	class	_T_Iterator
		: public _T_CIterator
		{
			friend	_vector_base<_Ty, _Alc>;
			typedef	_T_Iterator		this_type;
			typedef	_T_CIterator	base_type;
		public:
			typedef base_type::iterator_category	iterator_category;
			typedef typename base_type::value_type			value_type;
			typedef typename base_type::difference_type		difference_type;
			typedef typename base_type::pointer				pointer;
			typedef typename base_type::reference			reference;
			typedef typename base_type::const_pointer		const_pointer;
			typedef typename base_type::const_reference		const_reference;

			LOLIX_INLINE_CALL	_T_Iterator(void): base_type(){}

			LOLIX_INLINE_CALL	reference operator* (void)const
				{
				return const_cast<reference>(base_type::operator *());
				}

			LOLIX_INLINE_CALL	pointer operator -> (void)const
				{
				return &(**this);
				}
			LOLIX_INLINE_CALL	this_type& operator++ (void)
				{
				base_type::operator++();
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix increment operator instead")
			LOLIX_INLINE_CALL	const this_type operator++(int)
				{
				this_type tmp(*this);
				++*this;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type& operator-- (void)
				{
				base_type::operator--();
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix decrement operator instead")
			LOLIX_INLINE_CALL	const this_type operator-- (int)
				{
				this_type tmp(*this);
				--*this;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type& operator += (difference_type pos)
				{
				base_type::operator += (pos);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type& operator -= (difference_type pos)
				{
				base_type::operator -= (pos);
				return *this;
				}

			LOLIX_INLINE_CALL	this_type	operator + (difference_type pos)const
				{
				this_type tmp(*this);
				tmp += pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type	operator - (difference_type pos)const
				{
				this_type tmp(*this);
				tmp -= pos;
				return tmp;
				}

			LOLIX_INLINE_CALL	difference_type	operator-(const this_type& o)const
				{
				DO_IN_DEBUG_MODEL(__check_same_ct(o));
				return this->__get() - o.__get();
				}

			LOLIX_INLINE_CALL	reference	operator [](difference_type pos)const
				{
				return const_cast<reference>(base_type::operator[](pos));
				}


		private:
			LOLIX_INLINE_CALL	_T_Iterator(const _vector_base<_Ty, _Alc>& o, size_type pos)
				: _T_CIterator(o, pos)
				{ }
			using base_type::__get;
			LOLIX_INLINE_CALL	pointer __get(void)
				{
				return const_cast<pointer>(base_type::__get());
				}
		};
	friend	_T_Iterator;

public:
	typedef	_T_CIterator	const_iterator;
	typedef	_T_Iterator		iterator;
	typedef	std::reverse_iterator<iterator>			reverse_iterator;
	typedef	std::reverse_iterator<const_iterator>	const_reverse_iterator;

protected:
	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(void): _val(0), _size(0), _capacity(0), _alc(){ }
	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(const allocator_type& alc)
		: _val(0), _size(0), _capacity(0), _alc(alc)
		{}
	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(size_type	in_cnt)
		: _val(0), _size(0), _capacity(0), _alc()
		{
		reserve(in_cnt);
		value_type tmp = value_type();
		_size = _X_Construct(_val, make_value_iterator(&tmp), in_cnt);
		}
	template <typename _TR>
	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(size_type	in_cnt, const _TR& in_val)
		: _val(0), _size(0), _capacity(0), _alc()
		{
		reserve(in_cnt);
		_size = _X_Construct(_val, make_value_iterator(&in_val), in_cnt);
		}

	template <typename _TR>
	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(size_type in_cnt, const _TR& in_val, const allocator_type& alc)
		: _val(0), _size(0), _capacity(0), _alc(alc)
		{
		reserve(in_cnt);
		_size = _X_Construct(_val, make_value_iterator(&in_val), in_cnt);
		}

	template<typename Ipt>
	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(Ipt in_fst, Ipt in_lst)
		: _val(0), _size(0), _capacity(0), _alc()
		{
		const difference_type diff = std::distance(in_fst, in_lst);
		reserve((size_type)diff);
		_size = _X_Construct(_val, in_fst, in_lst);
		}


	template<typename Ipt>
	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(Ipt in_fst, Ipt in_lst, const allocator_type& alc)
		: _val(0), _size(0), _capacity(0), _alc(alc)
		{
		const difference_type diff = std::distance(in_fst, in_lst);
		reserve((size_type)diff);
		_size = _X_Construct(_val, in_fst, in_lst);
		}

	LOLIX_INLINE_CALL	_vector_base<_Ty, _Alc>(const this_type& other)
		: _val(0), _size(other._size), _capacity(other._size), _alc(other._alc)
		{
		if ( _size )
			{
			_val = _alc.allocate(_capacity);
			for ( size_type i = 0; i != _size; ++i )
				_alc.construct(_val+i, other[i]);
			}
		}

	LOLIX_INLINE_CALL	this_type& operator = ( const this_type& o)
		{
		if ( this == &o )
			return *this;

		this_type tmp(o);
		this->swap(tmp);
		return *this;
		}
	LOLIX_INLINE_CALL	~_vector_base<_Ty, _Alc>(void)
		{
		clear();
		}
public:
	LOLIX_INLINE_CALL	void assign(size_type in_cnt, const_reference v)
		{
			this->assign(make_value_iterator(&v, 0), make_value_iterator(&v, in_cnt));
		}

	template<typename InputIter>
	LOLIX_INLINE_CALL	void assign(InputIter f, InputIter e)
		{
		this_type tmp(f, e, _alc);
		this->swap(tmp);
		}

	//LOLIX_WARNING_FOR_NO_STANDARD("this function don't throw except")
	LOLIX_INLINE_CALL	_Ty& at(size_type pos)
		{
		if ( in_pos >= size() )
			{
				__LOLIX_THROW__(return (_Ty*)0, throw LOLIX_CFG__STD_EXCEPT_NAME_SPACE(out_of_range)("out of range during 'at'"));
			}
		return (*this).operator[]();
		}

	//LOLIX_WARNING_FOR_NO_STANDARD("this function don't throw except")
	LOLIX_INLINE_CALL	const _Ty& at(size_type _Pos)const
		{
		return const_cast<this_type*>(this)->at();
		}

	LOLIX_INLINE_CALL	_Ty& back(void)
		{
		return (*this).operator[](size()-1);
		}

	LOLIX_INLINE_CALL	const _Ty& back(void)const
		{
		return (*this).operator[](size()-1);
		}

	LOLIX_INLINE_CALL	iterator begin(void)
		{
		return iterator(*this, 0);
		}
	LOLIX_INLINE_CALL	const_iterator begin(void)const
		{
		return const_iterator(*this, 0);
		}
	LOLIX_INLINE_CALL	size_type	capacity(void)const
		{
		return _capacity;
		}

	LOLIX_INLINE_CALL	void clear(void)
		{
		_X_Destroy(begin(), end());
		_alc.deallocate(_val, _capacity);
		_val = 0;
		_capacity = 0;
		}

	LOLIX_INLINE_CALL	bool empty(void)const
		{
		return _size == 0;
		}

	LOLIX_INLINE_CALL	iterator end(void)
		{
		return iterator(*this, _size);
		}
	LOLIX_INLINE_CALL	const_iterator end(void)const
		{
		return const_iterator(*this, _size);
		}

	LOLIX_INLINE_CALL	iterator erase(iterator in_where)
		{
		erase(in_where, in_where+1);
		return in_where;
		}

	LOLIX_INLINE_CALL	void erase(iterator in_fst, iterator in_lst)
		{
		DO_IN_DEBUG_MODEL(in_fst.__check_same_ct(begin()));
		DO_IN_DEBUG_MODEL(in_lst.__check_same_ct(begin()));
		LOLIX_ASSERT( in_fst >= begin() && in_lst <= end() && in_fst <= in_lst, "lolix::toy::vector::erase error, invalid param." );
		_X_Move_F(in_fst, in_lst, end());
		_X_Destroy(end() - (in_lst - in_fst), end());
		}

	LOLIX_INLINE_CALL	reference	front(void)
		{
		return *begin();
		}

	LOLIX_INLINE_CALL	const_reference	front(void)const
		{
		return *begin();
		}

	LOLIX_INLINE_CALL	allocator_type get_allocator(void)const
		{
		return _alc;
		}

	template<typename _TR, typename _ALC>
	LOLIX_INLINE_CALL	void insert(iterator in_where, const vector<_TR, _ALC>& o)
		{
		insert(in_where, o.begin(), o.end());
		}

	template<typename _TR>
	LOLIX_INLINE_CALL	iterator insert(iterator in_where, const _TR& _Val)
		{
		difference_type pos = in_where - begin();
		insert<size_type, _TR>(in_where, (size_type)1, _Val);
		return begin() + pos;
		}

	template<typename _SIZE_TYPE, typename _TR>
	LOLIX_INLINE_CALL	void insert(iterator in_where, _SIZE_TYPE _Count, const _TR& _Val)
		{
		__Insert_by_number(in_where, make_value_iterator(&_Val, 0)/*, make_value_iterator(&_Val, _Count)*/, _Count);
		}

	template<class Ipt>
	LOLIX_INLINE_CALL	void insert(iterator in_where, Ipt in_fst, Ipt in_lst)
		{
		difference_type cnt_diff = std::distance(in_fst, in_lst);
		LOLIX_ASSERT(cnt_diff >= 0, "insert invalid data here. diff == %I"LOLIX_CFG__SIZE_TYPE_BITS_SIZE_STRING"u", cnt_diff);
		return __Insert_by_number(in_where, in_fst/*, in_lst*/, (size_type)cnt_diff);
		}

	LOLIX_INLINE_CALL	size_type	max_size(void)const
		{
		return _alc.max_size();
		}

	LOLIX_INLINE_CALL	void		pop_back(void)
		{
		erase(--end());
		}

	template<typename _TR>
	LOLIX_INLINE_CALL	void		push_back(const _TR& in_val)
		{
		__Reserve(_size + 1);
		_X_Construct(_val+_size, &in_val, (size_type)1);
		++_size;
		}

	LOLIX_INLINE_CALL	reverse_iterator	rbegin(void)
		{
		return reverse_iterator(end());
		}

	LOLIX_INLINE_CALL	const_reverse_iterator rbegin(void)const
		{
		return const_reverse_iterator(end());
		}

	LOLIX_INLINE_CALL	reverse_iterator	rend(void)
		{
		return reverse_iterator(begin());
		}

	LOLIX_INLINE_CALL	const_reverse_iterator rend(void)const
		{
		return const_reverse_iterator(begin());
		}

	LOLIX_INLINE_CALL	void	resize(size_type in_new_size)
		{
		if ( in_new_size > _size )
			{
			__Reserve(in_new_size);
			value_type tmp/* = value_type()*/;
			_X_Construct(_val + _size, make_value_iterator(&tmp), in_new_size - _size);
			_size = in_new_size;
			}
		else
			{
			_X_Destroy(begin() + in_new_size, end());
			}
		}

	template<typename _T_in>
	//LOLIX_INLINE_CALL	void	resize(size_type	in_new_size, typename lolix::type::pass_type<_T_in>::const_value_type in_val)
	LOLIX_INLINE_CALL	void	resize(size_type	in_new_size, const _T_in& in_val)
		{
		if ( in_new_size > _size )
			{
			__Reserve(in_new_size);
			_X_Construct(_val + _size, make_value_iterator(&in_val), in_new_size - _size);
			_size = in_new_size;
			}
		else
			{
			_X_Destroy(begin() + in_new_size, end());
			}
		}

	LOLIX_INLINE_CALL	void	reserve(size_type in_new_capacity)
		{
		if ( in_new_capacity <= _capacity )
			return;
		this_type tmp(_alc);
		tmp._val = _alc.allocate(in_new_capacity);
		if ( !tmp._val )
			__LOLIX_THROW__(return, throw LOLIX_CFG__STD_EXCEPT_NAME_SPACE(bad_alloc)("bad alloc during reserve"));
		tmp._capacity = in_new_capacity;
		_X_Construct(tmp._val, const_cast<const this_type*>(this)->begin(), const_cast<const this_type*>(this)->end());
		tmp._size = _size;

		this->swap(tmp);
		}

	LOLIX_INLINE_CALL	size_type	size(void)const
		{
		return _size;
		}

	LOLIX_INLINE_CALL	void	swap(this_type& o)
		{
		if ( _alc == o._alc )
			{
			lolix::swap(_val, o._val);
			lolix::swap(_size, o._size);
			lolix::swap(_capacity, o._capacity);
			}
		else
			{
			this_type tmp(*this); (*this) = o; o = tmp;
			}
		}

	LOLIX_INLINE_CALL	reference	operator[](size_type pos)
		{
		LOLIX_ASSERT(pos < _size, "vector subscript out of range");
		return _val[pos];
		}

	LOLIX_INLINE_CALL	const_reference	operator[](size_type pos)const
		{
		LOLIX_ASSERT(pos < _size, "vector subscript out of range [%I"LOLIX_CFG__SIZE_TYPE_BITS_SIZE_STRING"u/%I"LOLIX_CFG__SIZE_TYPE_BITS_SIZE_STRING"u]", pos, _size);
		return _val[pos];
		}

	template<typename _Tv, typename _Talc>
	bool	operator == (const _vector_base<_Tv, _Talc>& o)const
		{
		if ( size() != o.size() )
			return false;
		for ( size_type i = 0; i != size(); ++i )
			if ( _val[i] != o._val[i] )
				return false;
		return true;
		}

	template<typename _Tv, typename _Talc>
	bool	operator != (const _vector_base<_Tv, _Talc>& o)const
		{
		return !((*this) == o);
		}

protected:
	template<class Ipt>
	LOLIX_INLINE_CALL	void __Insert_by_number(iterator in_where, Ipt in_fst/*, Ipt in_lst*/, size_type cnt_diff)
		{
		//0.	ABCDEF
		//1.	ABCDEF__	//	reserve
		//2.	ABCDEFef	//	construct old
		//3.	ABCDcdef	//	move
		//4.	AB12cdef	//	copy

		//0.	ABCD
		//1.	ABCD____	//	reserve
		//2.	ABCD__CD	//	construct old
		//4.	AB12__CD	//	copy
		//5.	AB1234CD	//	construct new

		DO_IN_DEBUG_MODEL(in_where.__check_same_ct(begin()));
		LOLIX_ASSERT(in_where <= end() && in_where >= begin(), "vector iterator out of range.");
		if ( !cnt_diff )
			return;

		const size_type iw = in_where - begin();
		const size_type	cnt = (size_type)cnt_diff;
		//	1. reserve
		__Reserve(_size + cnt);
		if ( iw + cnt <= _size )
			{
		//	2. construct old
			size_type src_begin = _size - cnt;
			size_type dec_begin = _size;
			size_type opt_size = cnt;
			_X_Construct(_val+dec_begin, _val + src_begin, opt_size);
		//	3. move
			src_begin = iw;
			opt_size = _size - iw - cnt;
			dec_begin = _size - opt_size;
			_X_Move_B( begin() + dec_begin, begin() + src_begin, begin() + src_begin + opt_size );
		//	4. copy
			dec_begin = iw;
			opt_size = cnt;
			_X_Copy( begin() + dec_begin, in_fst, opt_size );
			}
		else
			{
		//	2. construct old
			size_type src_begin = iw;
			size_type opt_size = _size - iw;
			size_type dec_begin = iw + cnt;
			_X_Construct(_val + dec_begin, _val + src_begin, opt_size);
		//	4. copy
			dec_begin = iw;
			opt_size = _size - iw;
			_X_Copy(begin()+dec_begin, in_fst, opt_size);

		//	5.	construct new
			Ipt	c_new_iter_begin( _Add_Iterator_Distance(in_fst, opt_size, std::iterator_traits<Ipt>::iterator_category()) );
			dec_begin = _size;
			opt_size = cnt - opt_size;
			_X_Construct(_val + dec_begin, c_new_iter_begin, opt_size);
			}
		_size += cnt;
		}


private:
	LOLIX_INLINE_CALL	void __Reserve(size_type st)
		{
		size_type new_capacity = ((_capacity+1) << 1);
		if ( st > _capacity )
			reserve( st > new_capacity? st: new_capacity );
		}
	LOLIX_INLINE_CALL	void _X_Move_F(iterator dec, iterator src_begin, iterator src_end)
		{
		for ( ; src_begin != src_end; ++src_begin, ++dec )
			*dec = *src_begin;
		}
	LOLIX_INLINE_CALL	void _X_Move_B(iterator dec, iterator src_begin, iterator src_end)
		{
		iterator dec_end = dec + (src_end - src_begin);
		while ( dec_end > dec )
			*--dec_end = *--src_end;
		}

	template<typename Ipt>
	LOLIX_INLINE_CALL	void _X_Copy(iterator in_where, Ipt in_fst, size_type in_cnt)
		{
		for ( size_type st = 0; st != in_cnt; ++st, ++in_where, ++in_fst )
			*in_where = *in_fst;
		}

	//	构造， 不改变当前的 size()
	template<typename _SIZE_TYPE, typename Ipt>
	LOLIX_INLINE_CALL	size_type _X_Construct(pointer in_where, Ipt in_fst, _SIZE_TYPE in_cnt)
		{
		for ( size_type st = 0; st != in_cnt; ++st, ++in_where, ++in_fst )
			_alc.construct(in_where, *in_fst);
		return in_cnt;
		}

	template<typename Ipt>
	LOLIX_INLINE_CALL	size_type _X_Construct(pointer in_where, Ipt in_fst, Ipt in_lst)
		{
		return _X_Construct(in_where, in_fst, in_lst, std::iterator_traits<Ipt>::iterator_category());
		}
	template<typename Ipt>
	LOLIX_INLINE_CALL	size_type _X_Construct(pointer in_where, Ipt in_fst, Ipt in_lst, std::random_access_iterator_tag)
		{
		const size_type rtv = in_lst - in_fst;
		for ( ; in_fst != in_lst; ++in_where, ++in_fst)
			_alc.construct(in_where, *in_fst);
		return rtv;
		}
	template<typename Ipt, typename _O>
	LOLIX_INLINE_CALL	size_type _X_Construct(pointer in_where, Ipt in_fst, Ipt in_lst, _O)
		{
		size_type st_size = 0;
		for ( ; in_fst != in_lst; ++in_where, ++in_fst, ++st_size )
			_alc.construct(in_where, *in_fst);
		return st_size;
		}

	LOLIX_INLINE_CALL	size_type _X_Construct(pointer in_where, size_type in_cnt)
		{
		for ( size_type st = 0; st != in_cnt; ++st, ++in_where )
			_alc.construct(in_where);
		return in_cnt;
		}

	template<typename Ipt>
	LOLIX_INLINE_CALL	Ipt _Add_Iterator_Distance(Ipt in_fst, difference_type Cnt, std::random_access_iterator_tag)
		{
		return in_fst + Cnt;
		}

	template<class Ipt, typename _T_O>
	LOLIX_WARNING_FOR_PERFORMANCE("use random_access_iterator for speed")
	LOLIX_INLINE_CALL	Ipt _Add_Iterator_Distance(Ipt in_fst, difference_type in_cnt, _T_O)
		{
		for ( difference_type i = 0; i != in_cnt; ++i, ++in_fst )
			;
		return in_fst;
		}

	//	改变当前 size()
	void _X_Destroy(iterator in_fst, iterator in_lst)
		{
		DO_IN_DEBUG_MODEL(in_fst.__check_same_ct(begin()));
		DO_IN_DEBUG_MODEL(in_lst.__check_same_ct(begin()));
		LOLIX_ASSERT( in_fst >= begin() && in_lst <= end() && in_fst <= in_lst, "lolix::toy::vector::_X_Destroy error, invalid param." );

		difference_type ct = in_lst - in_fst;
		for ( ; in_fst != in_lst; ++in_fst )
			{
			_alc.destroy(in_fst.__get());
			}
		_size -= ct;
		}
private:
	pointer		_val;
	size_type	_size;		//	数据大小
	size_type	_capacity;	//	缓冲区长度
	_Alc		_alc;
};
}

template< typename _Ty, typename _Alc = allocator<_Ty> >
class vector
: public _help::_vector_base<_Ty, typename _Alc::rebind<_Ty>::other>
{
	typedef	vector<_Ty, _Alc>	this_type;
	typedef	_help::_vector_base<_Ty, typename _Alc::rebind<_Ty>::other> base_type;
public:
	typedef				_Alc allocator_type;
	typedef typename	base_type::size_type		size_type;
	typedef typename	base_type::difference_type	difference_type;
	typedef typename	base_type::pointer			pointer;
	typedef typename	base_type::const_pointer	const_pointer;
	typedef typename	base_type::reference		reference;
	typedef typename	base_type::const_reference	const_reference;
	typedef typename	base_type::value_type		value_type;
	typedef	typename	base_type::const_iterator	const_iterator;
	typedef	typename	base_type::iterator			iterator;
	typedef	typename	base_type::reverse_iterator	reverse_iterator;
	typedef	typename	base_type::const_reverse_iterator	const_reverse_iterator;

	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(void): base_type(){ }
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(const this_type& o): base_type(o){ }
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(const allocator_type& alc): base_type(alc){}

	template<typename Tp>
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(const Tp& tp): base_type(tp)		{}
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(size_type	in_cnt): base_type(in_cnt)	{}
	template<typename _TR>
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(size_type	in_cnt, const _TR& in_val): base_type(in_cnt, in_val){}
	template<typename _TR>
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(size_type in_cnt, const _TR& in_val, const allocator_type& alc): base_type(in_cnt, in_val, alc){}
	template<typename Ipt>
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(Ipt in_fst, Ipt in_lst): base_type(in_fst, in_lst){}
	template<typename Ipt>
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(Ipt in_fst, Ipt in_lst, const allocator_type& alc): base_type(in_fst, in_lst, alc){}
	LOLIX_INLINE_CALL	vector<_Ty, _Alc>(const base_type& other): base_type(other){}
	LOLIX_INLINE_CALL	this_type& operator = ( const base_type& o)
		{
		if ( this == &o )
			return *this;

		this_type tmp(o);
		this->swap(tmp);
		return *this;
		}
	LOLIX_INLINE_CALL	~vector<_Ty, _Alc>(void)
		{
		}
	LOLIX_INLINE_CALL	void	swap(base_type& o)
		{
		base_type::swap(o);
		}
};

}}

namespace lolix{
	template <class _Ty, class _Alloc>
	LOLIX_INLINE_CALL void swap(toy::_help::_vector_base<_Ty, _Alloc>& tl, toy::_help::_vector_base<_Ty, _Alloc>& tr)
	{ tl.swap(tr); }
	template <class _Ty, class _Alloc>
	LOLIX_INLINE_CALL void swap(toy::vector<_Ty, _Alloc>& tl, toy::vector<_Ty, _Alloc>& tr)
	{ tl.swap(tr); }
}

#undef		__LOLIX_TMP__DEFINE__CHECK_VALID
//--------------------------------------------------------------------------
//==============================================================================
#endif	//	!defined(__LOLIX__TOY__STD_VECTOR__NICK__K_IN_G__)
